In [1]:
import matplotlib.pyplot as plt
import numpy as np
""" statistical data visualization packages"""
import seaborn as sns
""" seaborn configurations """
sns.set_style('white')
sns.set_context('talk')
sns.set(font_scale=2)
plt.rcParams['figure.figsize'] = 20, 10
If $f(n) = o(g(n))$, then $\exists$ positive constants $c$, $n_0$, such that $0 \leq f(n) < c\cdot g(n)$, $\forall \;\; n \geq n_0$. - strict upper bound
If $f(n) = O(g(n))$, then $\exists$ positive constants $c$, $n_0$, such that $0 \leq f(n) \leq c\cdot g(n)$, $\forall \;\; n \geq n_0$. upper bound
If $f(n) = \Theta (g(n))$, then $\exists$ positive constants $c_1$, $c_2$, $n_0$, such that $0 \leq c_1\cdot g(n) \leq f(n) \leq c_2\cdot g(n)$, $\forall \;\; n \geq n_0$. upper and lower bound
If $f(n) = \Omega(g(n))$, then $\exists$ positive constants $c$, $n_0$, such that $0 \leq c\cdot g(n) \leq f(n)$, $\forall \;\; n \geq n_0$. lower bound
If $f(n) = \omega(g(n))$, then $\exists$ positive constants $c$, $n_0$, such that $0 \leq c\cdot g(n) < f(n)$, $\forall \;\; n \geq n_0$. strict lower bound
Thanks to Dra. Nina Amenta, her work available at http://web.cs.ucdavis.edu/~amenta/w04/dis1.pdf helped to develop this study.
disto podemos concluir, para que à partir de $n_0 = 1$ tenhamos como limite superior de $n^2$ sobre $f(n)$, $c$ deve assumir o valor de $30$.
Podemos analisar isto no gráfico gerado abaixo:
In [2]:
def graph(formula, x_range):
x = np.array(x_range)
y = eval(formula)
plt.plot(x,y, label=formula)
def generate(f, g, x1 = 3, x2 = 300):
plt.subplot(211)
r = np.linspace(0,x2,3001)
graph(f, r)
graph(g, r)
plt.legend(bbox_to_anchor=(0., 1.02, 1., .102), loc=3,
ncol=2, mode="expand", borderaxespad=0.)
plt.subplot(223)
r = np.linspace(0,x1,3001)
graph(f, r)
graph(g, r)
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()
c = 30
f = 'x**2 + 10*x + 20'
g = str(c)+'*x**2'
generate(f, g, x2 =15)
Vemos no gráfico acima como $30\cdot n^2$ domina $n^2+10n+20$ $\in$ $O(n^2)$. Lembrando que a visualização serve somente para auxiliar, a prova foi a matemática feita anterioremente.
Tendo $n_0 = 1$ e $c = 30$ fica comprovado que $n^2+10n+20$ $\in$ $O(n^2)$
Logo, sabendo que $\theta$ é uma quantia entre $0$ e $1$ e será dividido por $3$, então existe um $c$ inteiro positivo tal que $\lceil n/3 \rceil = O(n)$.
Analisando o resultado, e sabendo que $\theta$ é uma quantia entre $0$ e $1$ que irá dividir $3$, então não existe um $c$ inteiro positivo tal que $n = O(\lfloor n/3 \rfloor)$. Logo, não é verdade que $n$ $\in$ $O(\lfloor n/3\rfloor)$.
Vou considerar que quando não há base discreta no $\log$ a sua base é 10.
$$\begin{array}{rl} f(n) = \log_10 n & = O(\log_{10} n)\\ \log_{10} n & \leq c \cdot \log_{10} n\\ \log_{10} n & \leq \log_{10} n^c\\ n & \leq n^c\\ 1 & \leq \dfrac{n^c}{n}\\ 1 & \leq n^{c-1} \end{array}$$Aplicando $\lim\limits_{n\rightarrow\infty}$ obtemos:
$$\begin{array}{rl} \lim\limits_{n\rightarrow\infty} 1 & \leq \lim\limits_{n\rightarrow\infty} n^{c-1}\\ 1 & \leq \infty \;\; \text{(o que é verdade)}\\ \end{array}$$Analisando o resultado, e sabendo que $n^c$ sempre será maior ou igual à $n$, é possível concluir que existe um $c$ inteiro positivo tal que $n\log_10 n = O(\log_{10} n)$. Por exemplo, $n = n_0 = 1$ e $c = 10$.
$$\begin{array}{rl} n & \leq n^c 1 & \leq 1^{10}\\ 1 & \leq 1\\ \end{array}$$Logo, é verdade que $\log n$ $\in$ $O(\log_{10} n)$.
In [3]:
c = 10
f = 'np.log10(x)'
g = str(c) + '*np.log10(x)'
generate(f, g)
Aplicando $\lim\limits_{n\rightarrow\infty}$ obtemos:
$$\begin{array}{rl} \lim\limits_{n\rightarrow\infty} 1 & \geq \lim\limits_{n\rightarrow\infty} \dfrac{2^{\log_2(n) - n}}{c}\\ 1 & \geq \dfrac{2^{- \infty}}{c}\\ 1 & \geq 0 \;\; \text{(o que é verdade)}\\ \end{array}$$Analisando o resultado, e sabendo que $\log_2(n) - n$ é um valor negativo, e, consequentemente, o resultado de $2^{\log_2(10) - 10}$ será um número entre $0$ e $1$. Por exemplo, se eu escolher $n = n_0 = 10$ teremos:
$$\begin{array}{rl} c & \geq 2^{\log_2(10) - 10}\\ c & \geq 2^{−6,678071905}\\ c & \geq 0,009765625 \end{array}$$logo existe um $c$ inteiro positivo (exemplo, $c = 1$ para $n_0 = 10$) tal que $n = O(2^n)$. Logo, $n$ $\in$ $O(2^n)$.
In [4]:
c = 1
f = 'x'
g = str(c) + '*2**x'
generate(f, g, x2 = 15)
Aplicando $\lim\limits_{n\rightarrow\infty}$ obtemos:
$$\begin{array}{rl} \lim\limits_{n\rightarrow\infty} 1 & \leq \lim\limits_{n\rightarrow\infty} \dfrac{10^{cn}}{n}\\ 1 & \leq \lim\limits_{n\rightarrow\infty} \dfrac{c \cdot 10^{cn-1}}{1} \;\; \text{(utilizando l'hopital)}\\ 1 & \leq \infty \;\; \text{(o que é verdade)}\\ \end{array}$$Analisando o resultado, e sabendo que $10^{nc}$ é um valor sempre maior que $n$. Por exemplo, se eu escolher $n = n_0 = 10$ e $c = 1$ teremos:
$$\begin{array}{rl} 10 & \leq 10^{10\cdot 1} \\ 10 & \leq 10000000000 \\ \end{array}$$logo existe um $c$ inteiro positivo (exemplo, $c = 1$ para $n_0 = 10$) tal que $\log n = O(n)$. Logo, $\log n$ $\in$ $O(n)$.
In [5]:
c = 1
f = 'np.log10(x)'
g = str(c) + '*x'
generate(f, g, x2=50)
Aplicando $\lim\limits_{n\rightarrow\infty}$ obtemos:
$$\begin{array}{rl} \lim\limits_{n\rightarrow\infty} 1 & \leq \lim\limits_{n\rightarrow\infty} \dfrac{ 1000\cdot c}{n}\\ 1 & \leq \dfrac{1000\cdot c}{\infty} \\ 1 & \leq 0\;\; \text{(o que é falso)}\\ \end{array}$$Analisando o resultado, e sabendo que $10^{nc}$ é um valor sempre maior que $n$. Por exemplo, se eu escolher $n = n_0 = 10$ e $c = 1$ teremos:
$$\begin{array}{rl} 10 & \leq 10^{10\cdot 1} \\ 10 & \leq 10000000000 \\ \end{array}$$logo não existe um $c$ inteiro positivo (exemplo, $c = 1$ para $n_0 = 10$) tal que $\log n = O(n)$. Logo, $\log n$ $\notin$ $O(n)$.
Aplicando $\lim\limits_{n\rightarrow\infty}$ obtemos:
$$\begin{array}{rl} \lim\limits_{n\rightarrow\infty} 1 & \leq \lim\limits_{n\rightarrow\infty} \dfrac{2\cdot c}{n}\\ 1 & \leq \dfrac{2\cdot c}{\infty} \\ 1 & \leq 0\;\; \text{(o que é falso)}\\ \end{array}$$Analisando o resultado, definindo $c = 1$, obtemos que qualquer valor acima de $n = n_0 = 2$, a desigualdade $n \leq 2\cdot c$ se torna falsa . Por exemplo, se eu escolher $n = n_0 = 10$ e $c = 1$ teremos:
$$\begin{array}{rl} 10 & \leq 2\cdot 1 \\ 10 & \leq 2\;\; \text{(o que é falso)} \\ \end{array}$$logo não existe um $c$ inteiro positivo (exemplo, $c = 1$ para $n_0 = 10$) tal que $\log n = O(n)$. Logo, $\log n$ $\notin$ $O(n)$.
In [6]:
c = 1
f = '0.5*x**2'
g = str(c) + '*x'
generate(f, g, x2 = 10)
?
$$\begin{array}{rl} T(n) & = O(1)\\ T(n) & \leq c' \cdot 1\\ T(n) & \leq c' \cdot 1\\ \end{array}$$?
Aplicando $\lim\limits_{n\rightarrow\infty}$ obtemos:
$$\begin{array}{rl} \lim\limits_{n\rightarrow\infty} \left(1 + \dfrac{999}{n} + \dfrac{9999}{n^2}\right) & \leq \lim\limits_{n\rightarrow\infty} c\\ 1 + \dfrac{999}{\infty} + \dfrac{9999}{\infty^2} & \leq c \\ 1 + 0 + 0 & \leq c\\ 1 & \leq c\;\; \text{(o que é verdadeiro para $c \geq 1$)}\\ \end{array}$$Analisando o resultado, definindo $c = 876$, obtemos que qualquer valor acima de $n = n_0 = 4$, a desigualdade $n^2 + 999n + 9999 \leq c \cdot n^2$ se torna verdadeira . Por exemplo, se eu escolher $n = n_0 = 4$ e $c = 876$ teremos:
$$\begin{array}{rl} 1 + \dfrac{999}{n} + \dfrac{9999}{n^2} & \leq c \\ 1 + \dfrac{999}{4} + \dfrac{9999}{4^2} & \leq 876 \\ 875,6875& \leq 876 \\ \end{array}$$logo existe um $c$ inteiro positivo (exemplo, $c = 876$ para $n_0 = 4$) tal que $n^2 + 999n + 9999 = O(n^2)$. Logo, $n^2 + 999n + 9999$ $\in$ $O(n^2)$.
In [7]:
c = 876
f = 'x**2 + 999*x + 9999'
g = str(c) + '*x**2'
generate(f, g, x1 = 10, x2 = 20)
Aplicando $\lim\limits_{n\rightarrow\infty}$ obtemos:
$$\begin{array}{rl} \lim\limits_{n\rightarrow\infty} 1 & \leq \lim\limits_{n\rightarrow\infty} (2\cdot c - 1)\cdot n\\ 1 & \leq \infty \;\; \text{(o que é verdadeiro para $c \geq 1$)}\\ \end{array}$$Analisando o resultado, definindo $c = 1$, obteremos $n$:
$$\begin{array}{rl} \dfrac{1}{n} & \leq 2\cdot c - 1 \\ \dfrac{1}{n} & \leq 2\cdot 1 - 1 \\ 1 & \leq n\cdot(2 - 1) \\ 1 & \leq n \\ \end{array}$$logo existe um $n = n_0 = 1$ $c = 1$ tal que $\dfrac{1}{2}n(n+1) \leq c \cdot n^2$. Logo, $\dfrac{1}{2}n(n+1)$ $\in$ $O(n^2)$.
In [8]:
c = 1
f = '(1/2)*x*(x+1)'
g = str(c) + '*x**2'
generate(f, g)
Aplicando $\lim\limits_{n\rightarrow\infty}$ obtemos:
$$\begin{array}{rl} \lim\limits_{n\rightarrow\infty} \left(\dfrac{1}{100}n - 999 - \dfrac{9999}{n}\right) & \leq \lim\limits_{n\rightarrow\infty} c\\ \dfrac{1}{100}\infty - 999 - \dfrac{9999}{\infty} & \leq c\\ \infty & \leq c \;\; \text{(o que é falso)}\\ \end{array}$$Analisando o resultado, é impossível obter um valor de $c$. Logo não existe um $c$ para que exista $n = n_0$ tal que $\dfrac{1}{100}n^2 - 999n - 9999 \leq c \cdot n$.
Logo, $\dfrac{1}{100}n^2 - 999n - 9999$ $\notin$ $O(n)$.
In [9]:
c = 1000
f = '(1/100)*x**2 - 999*x - 9999'
g = str(c) + '*x'
generate(f, g, x2= 250000)
Aplicando $\lim\limits_{n\rightarrow\infty}$ obtemos:
$$\begin{array}{rl} \lim\limits_{n\rightarrow\infty} \dfrac{\log_2n^2 - \log_2c}{n} & \leq \lim\limits_{n\rightarrow\infty} 1\\ \dfrac{\log_2\infty^2 - \log_2c}{\infty} & \leq 1\\ 0 & \leq 1 \;\; \text{(o que é verdadeiro)}\\ \end{array}$$Analisando o resultado, definindo $c = 1$, obteremos $n$:
$$\begin{array}{rl} \dfrac{\log_2n^2 - \log_2c}{n} &\leq 1\\ \dfrac{\log_2n^2 - \log_21}{n} &\leq 1\\ \dfrac{\log_2n^2 - 0}{n} &\leq 1\\ \dfrac{\log_2n^2}{n} &\leq 1\\ \log_2n^{2/n} &\leq 1\\ \log_22^{2/2} &\leq 1 \;\; \text{(substituindo $n = 2$)}\\ 1 &\leq 1\\ \end{array}$$logo existe um $n = n_0 = 2$ e $c = 1$ tal que $n^2 \leq c \cdot 2^n$. Logo, $n^2 = O(2^n)$.
In [10]:
c = 1
f = 'x**2'
g = str(c) + '*2**x'
generate(f, g, x2 = 8)
Aplicando $\lim\limits_{n\rightarrow\infty}$ obtemos:
$$\begin{array}{rl} \lim\limits_{n\rightarrow\infty} \dfrac{\log n}{n^{1/2}} & \leq \lim\limits_{n\rightarrow\infty} c\\ 0 & \leq c \;\; \text{(o que é verdade)}\\ \end{array}$$Analisando o resultado, definindo $c = 1$ e $n = 1$, obteremos $n$:
$$\begin{array}{rl} \dfrac{\log_2n^2 - \log_2c}{n} &\leq 1\\ \dfrac{\log_21^2 - \log_21}{1} &\leq 1\\ 0 &\leq 1\\ \end{array}$$logo existe um $n = n_0 = 1$ e $c = 1$ tal que $\log n \leq c \cdot n^{1/2}$. Logo, $\log n = O(\sqrt{n})$.
In [11]:
c = 1
f = 'np.log10(x)'
g = str(c) + '*np.sqrt(x)'
generate(f, g)
À partir deste ponto utilizarei a propriedade de W (Lambert W-Function) e o caso será tratado em dois casos, conforme abaixo:
$$\begin{array}{rl c rl} 0 < n & < \exp\left(-W\left(\dfrac{1}{8}\cdot(-\log(10))\right)\right) & \;\;\;\; & n & > \exp\left(-W_{-1}\left(\dfrac{1}{8}\cdot(-\log(10))\right)\right) \\ 0 < n & < 1,57231 & \;\;\;\; & n & > 6,5071 \\ \end{array}$$Para auxiliar nos cálculos acima utilizei wolfram
Logo temos dois intervalos em que $f(n) \leq g(n)$ quando $0 < n < 1,57231$ e $n > 6,5071$, logo temos para $n$ inteiro e positivos, $n = 1$ e $n \geq 7$. Podemos confirmar esse duplo intervalo nos gráficos abaixo:
In [13]:
c = 8
f = '64*x*np.log10(x)'
g = str(c) + '*x**2'
generate(f, g, x2 = 10)
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
Devo mostrar que existe $f(n)$ tal que:
Que devo fazer para mostrar que $A$ é mais eficiente que $B$?
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]: